package bintree.LeetCode;
//105. 从前序与中序遍历序列构造二叉树

//根据前序和中序还原二叉树

/**
 * 看博客 力扣二叉树题里面
 */
public class Num105_buildTree {

    public int index = 0;//表示当前出来到前序遍历数组里面的那个元素
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        //设计一个方法根据前序和中序还原二叉树
        return buildTreeHelper(preorder, inorder, 0, inorder.length);//左闭右开，所以没有减 1
    }

    /**
     * 每次从前序遍历中取出一个根节点，借助中序遍历的[left...right)还原二叉树，返回树的树根
     * 解析：相当于读一个根，就创建一个节点，然后看左节点，看左节点的左节点，一直左走到头。
     *  才开始返回。每次根据给你的中序数组和范围判断右节点的连接，然后一级级返回。
     *  判断返回节点根据范围和中序数组需不需要连接，需要就重新左左左走头，没有就再次返回。
     */
    private TreeNode buildTreeHelper(int[] preorder, int[] inorder, int left, int right) {
        //1.边界
        if(left > right){
            //左大于右，肯定没有节点
            return null;
        }
        //2.什么时候结束？
        if(index == preorder.length){
            return null;
        }
        
        //没结束，就创建新节点
        TreeNode root = new TreeNode(preorder[index]);
        index ++;//取到一个根节点，就往下走一步
        //需要创建一个方法，知道该根节点在中序数组中的索引位置
        int pos = find(root.val, inorder);
        root.left = buildTreeHelper(preorder, inorder,left, pos - 1);//左闭右开
        root.right = buildTreeHelper(preorder, inorder,pos + 1, right);//左闭右开
        
        return root;
    }

    /**
     * 在中序数组里面变量找到 val 对应的索引位置
     */
    private int find(int val, int[] inorder) {
        for (int i = 0; i < inorder.length; i++) {
            if(inorder[i] == val){
                return i;
            }
        }
        //用 -1 表示没找到
        return -1;
    }

}
